package sort;

import java.util.Arrays;

public class Quick {
    public static void sort(Comparable[] a) {
        int lo = 0;
        int hi = a.length - 1;
        sort(a, lo, hi);
    }

    // lo 到 hi  进行排序
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        // 分割
        int partition = partition(a, lo, hi);

        // 排序左
        sort(a, lo, partition);
        // 排序右
        sort(a, partition + 1, hi);
    }

    // 分组
    public static int partition(Comparable[] a, int lo, int hi) {
        // 基准值
        Comparable key = a[lo];
        // 左指针
        int left = lo;
        // 右指针
        int right = hi;
        while (true) {
            // 搜索右边比key 小的数
            while (less(key, a[--right])) {
                if (right == lo) {
                    // 找不到 搜搜结束
                    break;
                }
            }
            // 搜索左边 比key大的数
            while (less(a[++left], key)) {
                if (left == hi) {
                    // 找不到 结束
                    break;
                }
            }

            if (left >= right) {
                // 全部扫码结束
                break;
            } else {
                // 还没结束 交换值 并继续扫描
                exchange(a, left, right);
            }
        }
        // 交换最后right索引 和基准值
        exchange(a, lo, right);
        return right;
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    /**
     * 交换数组a 索引i 和 索引j 处的值
     */
    private static void exchange(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        Integer[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 8};
        Quick.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
